package 链表;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * https://leetcode-cn.com/leetbook/read/linked-list/jjhf6/
 * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 */
public class 环形链表 {
    class ListNode {
       int val;
       ListNode next;
       ListNode(int x) {
           val = x;
           next = null;
       }
    }

    /*
        设头节点到入环口的距离为a,入环口到第一次相遇点的距离是b,相遇点到入环口的距离为c
        则第一次相遇的时候，s走过的路程为 a+b  f走过的路程为a+b+c+b
        f每次走两步，所有路程也是s的两倍 -> 2(a+b) = a+b+c+b  -> a = c
        说明从起点到入环口的距离和第一次相遇点的距离到入环口的距离是相等的
        当他们第一次相遇后，只需要让一个指针指向头节点，另一个从相遇点开始走，直到他们俩相遇的时候，那个节点就是入环口
     */
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode slow = head,fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast) break; //第一次的相遇点
        }

        //判断是否有环
        if(fast==null || fast.next == null) return null;

        //有环的情况下，从相遇点到入环口的距离 == 头节点到入环口的距离
        fast = head;
        while(fast!=slow){
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }

    //集合做法
    public ListNode detectCycleSet(ListNode head) {
        if(head == null || head.next == null) return null;
        Set<ListNode> set = new HashSet<>();
        while(head!=null){
            if(!set.add(head)){
                return head;
            }
            set.add(head);
            head = head.next;
        }
        return null;
    }
}
